package ljl.alg.jianzhioffer.round2;

import commons.TreeNode;

import java.util.Arrays;
import java.util.LinkedList;

public class _37_codec_tree {
    
    /**
     * 正常需要两个序列才能恢复一个树，每个值还不能一样
     * 把 null 序列化进去是不是就不用两个序列了？
     * 1
     *  \
     *  2
     *
     *  1,null,2
     *
     *  读取：1 是 root，null 是左孩子，2 是右孩子？
     * */
    class Codec {
        
        // Encodes a tree to a single string.
        StringBuilder sb = new StringBuilder();
        public String serialize(TreeNode root) {
            if (root == null) return "null,";
            dfs(root);
            return sb.toString();
        }
        void dfs(TreeNode node) {
            if (node == null)
                sb.append("null,");
            else {
                sb.append(node.val).append(",");
                dfs(node.left);
                dfs(node.right);
            }
        }
        
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            String[] arr = data.split(",");
            return decode(new LinkedList<>(Arrays.asList(arr)));
        }
        
        TreeNode decode(LinkedList<String> list) {
            String val = list.poll();
            if ("null".equals(val))
                return null;
            TreeNode root = new TreeNode(Integer.parseInt(val));
            root.left = decode(list);
            root.right = decode(list);
            return root;
        }
    }
    
    // 路飞用层序遍历，他理由是：题目示例用的层序遍历
    // 我们也来试一下
    class Codec2 {
        
        public String serialize(TreeNode root) {
            StringBuilder sb = new StringBuilder();
            LinkedList<TreeNode> q = new LinkedList<>();
            q.offer(root);
            while (!q.isEmpty()) {
                TreeNode node = q.poll();
                if (node != null) {
                    sb.append(node.val).append(",");
                    q.offer(node.left);
                    q.offer(node.right);
                } else {
                    sb.append("null,");
                }
            }
            return sb.toString();
        }
        
        public TreeNode deserialize(String data) {
            if ("null,".equals(data)) return null;
            String[] arr = data.split(",");
            LinkedList<TreeNode> q = new LinkedList<>();
            TreeNode root = new TreeNode(Integer.parseInt(arr[0]));
            q.offer(root);
            // 奇妙之处，用 i 追踪恢复到哪了
            // 我用 i 追踪时一般都是不恰当的时候！
            int i = 1;
            while (!q.isEmpty()) {
                TreeNode node = q.poll();
                String val = arr[i++];
                if (!"null".equals(val)) {
                    node.left = new TreeNode(Integer.parseInt(val));
                    q.offer(node.left);
                }
                val = arr[i++];
                if (!"null".equals(val)) {
                    node.right = new TreeNode(Integer.parseInt(val));
                    q.offer(node.right);
                }
            }
            return root;
        }
    }
}
